The purpose of this article is to review the literature on the topic of deterministic VEHICLE ROUTING PROBLEM (VRP) and to give a review on the exact and approximate solution techniques. More specifically the approximate (meta-heuristic) solution techniques are classified into: tabu search, simulated annealing, genetic algorithm, evolutionary algorithm, hybrid algorithm, and Ant Colony Optimization. Each of these solution techniques is briefly discussed and a case study from the literature is presented.

This paper proposes an integer linear mathematical formulation for VEHICLE ROUTING PROBLEM (VRP), where the capital cost for deploying each VEHICLE is minimized together with other on-link transportation costs. The model has been formulated as a multi-commodity network flow model with capacity constraints. It is well known that the computational complexity to this type of PROBLEMs is NP-hard. Thus, the ACO algorithm, which has been known to be a powerful meta-heuristic algorithm for solving VRPs in large networks, has been adapted to solve the PROBLEM. Although the ACO algorithm has repeatedly been used to solve the capacitated VRP, it has a drawback that cannot consider the capital cost of each VEHICLE along with other operational costs of the VEHICLEs (associated with the total distance traveled within a day) in its initial form. More specifically, naturally it assumes that each VEHICLE returns to the depot if it becomes full or the demand finishes, each met first; this paper seeks to propose an adapted ACO algorithm in which this assumption is released. To assess the capability of the proposed model in large-scale networks, the case study of Mashhad city, consisting of 253 traffic analysis zones and over than 3800 links, has been considered. Results show that the proposed algorithm converges to near-to-optimal solutions within two seconds of cpu time, which is encouraging.

VEHICLE ROUTING PROBLEM is very important and logistic in combinatorial optimization. In this paper, an innovative algorithm that combines the colony of ants and mutation operation for VEHICLE ROUTING PROBLEM is presented.

The VEHICLE emissions mainly depend on the amount of consumed fuel، type of fuel and traveled distance. One way to combat with greenhouse gases and air pollution associated with oil consumption is to use alternative energy sources. However، the lack of infrastructures such as refueling stations is one of the major barriers to the adoption of alternative-fuel VEHICLEs. In this study، as an operational approach for transition period، we propose a model to extend the VEHICLE ROUTING PROBLEM to green VEHICLEs. This is a NP-Hard PROBLEM، and consequently it is very difficult to solve the real-world instances. Therefore، we propose a solving method based on benders decomposition that equipped with a set of valid inequalities. Implementation of proposed algorithm on randomly generated PROBLEMs leads to acceptable results in a reasonable time.

One of the challenging issues in today’s competitive world for servicing companies is uncertainty in some factors or parameters that they often derive from fluctuations of market price and other reasons. With regard to this subject, it would be essential to provide robust solutions in uncertain situations. This paper addresses an open VEHICLE ROUTING PROBLEM with demand uncertainty and cost of VEHICLE uncertainty. Bertsimas and Sim’s method has been applied to deal with uncertainty in this paper. In addition, a deterministic model of open VEHICLE ROUTING PROBLEM is developed to present a robust counterpart model. The deterministic and the robust model is solved by GAMS software. Then, the mean and standard deviations of obtained solutions were compared in different uncertainty levels in numerous numerical examples to investigate the performance of the developed robust model and deterministic model. The computational results show that the robust model has a better performance than the solutions obtained by the deterministic model.

This paper develops an MILP model, named Satisfactory-Green VEHICLE ROUTING PROBLEM. It consists of ROUTING a heterogeneous fleet of VEHICLEs in order to serve a set of customers within predefined time windows. In this model in addition to the traditional objective of the VRP, both the pollution and customers’ satisfaction have been taken into account. Meanwhile, the introduced model prepares an effective dashboard for decision-makers that determines appropriate routes, the best mixed fleet, speed and idle time of VEHICLEs. Additionally, some new factors evaluate the greening of each decision based on three criteria. This model applies piecewise linear functions (PLFs) to linearize a nonlinear fuzzy interval for incorporating customers’ satisfaction into other linear objectives. We have presented a mixed integer linear programming formulation for the S-GVRP. This model enriches managerial insights by providing trade-offs between customers’ satisfaction, total costs and emission levels. Finally, we have provided a numerical study for showing the applicability of the model.

The VEHICLE ROUTING PROBLEM with the capacity constraints was considered in this paper. It is quite difficult to achieve an optimal solution with traditional optimization methods by reason of the high computational complexity for large-scale PROBLEMs. Consequently, new heuristic or metaheuristic approaches have been developed to solve this PROBLEM. In this paper, we constructed a new heuristic algorithm based on the tabu search and adaptive large neighborhood search (ALNS) with several specifically designed operators and features to solve the capacitated VEHICLE ROUTING PROBLEM (CVRP). The effectiveness of the proposed algorithm was illustrated on the benchmark PROBLEMs.The algorithm provides a better performance on largescaled instances and gained advantage in terms of CPU time.In addition, we solved a real-life CVRP using the proposed algorithm and found the encouraging results by comparison with the current situation that the company is in.

The open VEHICLE ROUTING PROBLEM (OVRP) is a variance of the VEHICLE ROUTING PROBLEM (VRP) that has a unique character which is its open path form. This means that the VEHICLEs are not required to return to the depot after completing service. Because this PROBLEM belongs to the NP-hard PROBLEMs, many metaheuristic approaches like the ant colony optimization (ACO) have been used to solve OVRP in recent years. The versions of ACO have some shortcomings like its slow computing speed and local-convergence. Therefore, in this paper, we present an efficient hybrid elite ant system called EHEAS in which a new state transition rule, tabu search as an effective local search algorithm and a new pheromone updating rule are used for more improving solutions. These modifications avoid the premature convergence and make better solutions. Computational results on sixteen standard benchmark PROBLEM instances show that the proposed algorithm finds closely the best known solutions for most of the instances in which ten best known solutions are also found. In addition, EHEAS is comparable in terms of solution quality to the best performing published metaheuristics.